//
// Created by EmFi on 2023/5/14.
//

#ifndef DBMS_INTERNALNODE_H
#define DBMS_INTERNALNODE_H

#include <ostream>
#include "Node.h"

template <class K>
class InternalNode : public Node<K> {
protected:
    // 指针数组
    Node<K> **pointers;
public:
    explicit InternalNode(int order) : Node<K>(order) {
        this->type = NodeType::INTERNAL;
        // 初始化指针数组
        this->pointers = new Node<K>*[this->pointerCapacity];
        for (int i = 0; i < this->pointerCapacity; i++) {
            this->pointers[i] = nullptr;
        }
    }

    ~InternalNode() {
        for (int i = 0; i < this->pointerCapacity; i++) {
            delete this->pointers[i];
        }
        delete this->pointers;
    }

    // 将 key 插入到当前内部节点，并将 key 对应的指针设置为 node，默认将 node 插入到 key 右侧
    // node 既可以是内部节点，也可以是叶子结点
    bool insert(K key, Node<K> *node, bool addNextPointer = true) {
        // 如果当前内部结点已满，则插入失败
        if (this->length >= this->capacity) {
            return false;
        }

        // 寻找插入的位置
        int index = 0;
        while (key > this->keys[index] && index < this->length) {
            index++;
        }

        // 将 index 及其后面的键依次后移，空出当前位置
        for (int i = this->length; i >= index; i--) {
            this->keys[i] = this->keys[i - 1];
        }
        if (addNextPointer) {
            // 将 index 及其后面的指针依次后移，空出当前位置
            for (int i = this->length + 1; i >= index + 1; i--) {
                this->pointers[i] = this->pointers[i - 1];
            }
        } else {
            // 将 index 及其前面的指针依次后移，空出当前位置
            for (int i = this->length + 1; i >= index; i--) {
                this->pointers[i] = this->pointers[i - 1];
            }
        }

        // 把数据存入当前位置
        this->keys[index] = key;
        if (addNextPointer) {
            this->pointers[index + 1] = node;
        } else {
            this->pointers[index] = node;
        }

        // 将 node 的父节点设置为本节点
        node->setFather(this);

        this->length++;

        return true;
    }

    // 在当前内部结点中删除 key，以及该 key 对应的指针，默认删除 key 的右指针
    bool remove(K key, bool delNextPointer = true) {
        bool found = false;

        // 寻找删除的位置
        int index = 0;
        while (index < this->length) {
            if (key == this->keys[index]) {
                found = true;
                break;
            }
            index++;
        }

        // 如果没有找到，返回失败
        if (!found) {
            return false;
        }

        // 将 index 及其后面的节点依次前移
        for (int i = index; i < this->length - 1; i++) {
            this->keys[i] = this->keys[i + 1];
            this->keys[i + 1] = NULL;
        }
        // 将 index 及其后面的指针依次前移
        if (delNextPointer) {
            for (int i = index; i < this->length - 1; i++) {
                this->pointers[i + 1] = this->pointers[i + 2];
                this->pointers[i + 2] = nullptr;
            }
        } else {
            for (int i = index; i < this->length; i++) {
                this->pointers[i] = this->pointers[i + 1];
                this->pointers[i + 1] = nullptr;
            }
        }

        this->length--;

        return true;
    }

    // 根据插入的 key 分裂中间结点
    // 把分裂后数据剪切到 newNode 中，返回分裂后两个节点的父节点的键
    /*
     * V 的值从 1 开始
     * 分裂内部结点与分裂叶子结点的操作并不相同，因为内部结点有 2V 个键和 2V+1 个指针，如果单纯地一分为二，指针将无法分配
     * 根据插入的 key 判断：
     * 1. 如果 key 小于第 V 个键，则把第 V 个键提出来，其左右的键分别分到两个结点中
     * 2. 如果 key 大于第 V+1 个键，则把第 V+1 个键提出来，其左右的键分别分到两个结点中
     * 3. 如果 key 介于第 V 和 V+1 个键之间，则把 key 作为要提出的键，原来的键各分一半到两个结点中
     */
    K split(InternalNode<K> *newNode, K key) {
        // 如果要插入的键在第 V 和 V+1 个键值之间
        if (key > this->keys[this->order - 1] && key < this->keys[this->order]) {
            int moved = 0;
            for (int i = this->order; i < this->length; i++) {
                // 把第 V+1 到 2V 个键移到新结点中
                newNode->keys[moved] = this->keys[i];
                this->keys[i] = NULL;

                moved++;
            }
            moved = 0;
            // 最中间的指针留在原节点，且新节点中的指针位置从 1 开始
            for (int i = this->order + 1; i < this->length + 1; i++) {
                // 重新设置父亲节点
                this->pointers[i]->setFather(newNode);

                // 把第 V+2 到 2V+1 个指针移到新结点中
                newNode->pointers[moved + 1] = this->pointers[i];
                this->pointers[i] = nullptr;

                moved++;
            }

            // 重新设置两个节点的数据长度
            this->length = this->order;
            newNode->length = newNode->order;

            // 把原键值返回
            return key;
        }

        // 以下处理 key 小于第 V 个键或 key 大于第 V+1 个键的情况

        // 判断是提取第 V 还是 V+1 个键
        int position = 0;
        if (key < this->keys[this->order - 1]) {
            position = this->order - 1;
        } else {
            position = this->order;
        }

        // 把第 position 个键提出来，作为新的键值返回
        K newKey = this->keys[position];

        int moved = 0;
        for (int i = position + 1; i < this->length; i++) {
            // 把第 position+1 到 2V 个键移到新结点中
            newNode->keys[moved] = this->keys[i];
            this->keys[i] = NULL;

            moved++;
        }
        moved = 0;
        for (int i = position + 1; i < this->length + 1; i++) {
            // 重新设置父亲节点
            this->pointers[i]->setFather(newNode);

            // 把第 position+1 到 2V+1 个指针移到指定的结点中
            newNode->pointers[moved] = this->pointers[i];
            this->pointers[i] = nullptr;

            moved++;
        }

        this->keys[position] = NULL;

        // 重新设置两个节点的数据长度
        this->length = position;
        newNode->length = this->capacity - position - 1;

        return newKey;
    }

    // 合并内部结点，将指定内部结点的数据全部合并到本结点
    // merge 操作一定是从右侧节点合并到本节点
    bool merge(InternalNode<K> *node) {
        // 预留一个位置
        if (this->length + node->length + 1 > this->capacity) {
            return false;
        }

        // 将待合并节点的第 0 个指针的第 0 个键插入到当前节点
        this->insert(node->getPointer(0)->getKey(0), node->getPointer(0));

        for (int i = 0; i < node->length; i++) {
            // 由于另一个节点的数据顺序相当于本节点是未知的，因此调用 insert 方法进行插入
            this->insert(node->keys[i], node->pointers[i + 1]);
        }

        return true;
    }

    Node<K> *getPointer(int index) {
        return this->pointers[index];
    }

    void setPointer(int index, Node<K> *pointer) {
        this->pointers[index] = pointer;
    }

    friend ostream &operator<<(ostream &os, const InternalNode &node) {
        os << "{" << &node << "} ";
        for (int i = 0; i < node.length; i++) {
            os << "[" << node.pointers[i] << "] " << node.keys[i];
            if (i < node.length - 1) {
                os << " ";
            }
        }
        os << " [" << node.pointers[node.length] << "]";
        return os;
    }
};

#endif //DBMS_INTERNALNODE_H
